package com.heima.leetcode.practice;

/**
 * @description: leetcode 287. 寻找重复数
 * @author 勾新杰
 * @version 1.0
 * @date 2025/2/13 9:54
 */
public class E287 {

    /**
     * <h3>方法一：龟兔赛跑法，时间复杂度O(1), 空间复杂度O(1)</h3>
     * 由于数组中的值在1-n之间（nums总共n+1个数），也就是后面的索引，将其值当作索引，构建链表关系
     * @param nums 数组
     * @return 重复的数字
     */
    public int findDuplicate1(int[] nums) {
        // 1. 龟先走一步，兔子先走两步，注意，这里是从0开始走的，不是nums[0]
        int tortoise = nums[0], rabbit = nums[nums[0]];
        // 2. 直到龟和兔子相遇
        while(tortoise != rabbit){
            tortoise = nums[tortoise];
            rabbit = nums[nums[rabbit]];
        }
        // 3. 让兔子从起点(是0，不是nums[0])出发，龟和兔子每次走一步，直到相遇
        rabbit = 0;
        while(tortoise != rabbit){
            tortoise = nums[tortoise];
            rabbit = nums[rabbit];
        }
        // 4. 找到相遇点，就是重复的数字
        return rabbit;
    }

    /**
     * <h3>方法二：计数排序，时间复杂度O(n), 空间复杂度O(n)</h3>
     * @param nums 数组
     * @return 重复的数字
     */
    public int findDuplicate2(int[] nums) {
        int[] count = new int[nums.length];
        for (int num : nums){
            if (count[num] == 1) return num;
            count[num]++;
        }
        return -1;
    }
}
